package com.algrithom.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.common.model.Node;

/**
 * 图的拷贝
 */
class Solution3 {
    
    private final Map<Node,Node> visited = new HashMap<>();
    
    public static void main(String[] args){
        int[][] adjList = {{2,4},{1,3},{2,4},{1,3}};
        List<Node> list = new ArrayList<>();
        Node node = new Node(1,new ArrayList<>(1));
        node.getNeighbors().add(new Node(2,null));
        node.getNeighbors().add(new Node(4,null));
        list.add(node);
        
        node = new Node(2,new ArrayList<>(1));
        node.getNeighbors().add(new Node(1,null));
        node.getNeighbors().add(new Node(3,null));
        list.add(node);
        
        node = new Node(3,new ArrayList<>(1));
        node.getNeighbors().add(new Node(2,null));
        node.getNeighbors().add(new Node(4,null));
        list.add(node);
        
        node = new Node(4,new ArrayList<>(1));
        node.getNeighbors().add(new Node(1,null));
        node.getNeighbors().add(new Node(3,null));
        list.add(node);
        
        Solution3 solution3 = new Solution3();
        list.forEach(nd -> {
            Node node1 = solution3.cloneGraph(nd);
        });
    }
    
    public Node cloneGraph(Node node){
        if (node == null) {
            return node;
        }
        
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        
        Node cloneNode = new Node(node.getVal(),new ArrayList<>());
        visited.put(node,cloneNode);
        
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}
